package com.qf.arith;

import java.util.HashMap;
import java.util.Map;

/**
 *
 *     走阶梯，
 *        1、有n级阶梯，
 *        2、一次可以走一级、两级或者三级，
 *       请编写一个函数计算走完该阶梯一共有多少种方法。
 * @author lixu
 */
public class TestZJT {


    /**

     *
     *       50级  走法：过亿 了
     *
     * @param args
     */
    public static void main(String[] args) {

/*        long n = 10;//台阶的级数  274
        System.out.println("走法：" + f(n));
         long n = 50;//台阶的级数
        System.out.println("走法：" + f1(n));
        */

        long ct = System.currentTimeMillis();
        long n = 50;//台阶的级数
        System.out.println("走法：" + f1(n));
        System.out.println("耗时:" + (System.currentTimeMillis() - ct) + "ms");



    }

    /**
     * 走阶梯: 优化
     * 第二种办法：找规律遍历法
     *
     *
     *    1级：  走法：1
     *    2级：  走法：2
     *    3级：  走法：4
     *
     *
     *    4级：  走法：7
     *    5级：  走法：13
     *
     *    6级：  走法：24
     *    ....
     *
     *
     *    走法：10562230626642
     *     耗时:0ms
     *
     *
     *     走法：10562230626642
     *     耗时:1ms
     * @param n  时间复杂度： O(n)  空间复杂度 O(1)
     * @return
     */
    private static long f2(long n) {//50
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(n == 3){
            return 4;
        }

        long a=1,b=2,c=4,d=0;   //a=(i-3)级  b=(i-2)级  c=（i-1)级
        for (int i = 4; i <= n; i++) {
            //d=i级 //相加
            d = a + b + c;
            a=b;
            b=c;
            c=d;
        }
        //
        return d;
    }


    //本地缓存
    private static Map<Long,Long> cacheMap = new HashMap<>();//缓存 Key Value

    /**
     *  走阶梯: 优化
     *     1、加缓存
     *         Controller--》Service--》Dao--》Redis缓存
     *                                   如果有数据直接返回
     *                                   如果没有数据、再查询Mysql数据
     *                                   查询完成之后保存到缓存中一份 直接返回
     *                                   下一次再查询缓存 就有数据了
     * @param n   时间复杂度： O(n)  空间复杂度 O(n)
     * @return
     */
    private static long f1(long n) {//50
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(n == 3){
            return 4;
        }
        //大于等于4的时候
        //1:查缓存
        //cacheMap: Key：阶梯数   Value:走法的数量
        Long num = cacheMap.get(n);
        if(num != null){
            return num;
        }else{
            long l = f1(n - 1) + f1(n - 2) + f1(n - 3);
            //2:保存在缓存中
            cacheMap.put(n,l);
            //返回此数据
            return l;
        }
    }


    /**
     * 请编写一个函数计算走完该阶梯一共有多少种方法。
     *      * 分析：
     *      *    n级阶梯
     *      *    1、1级  走法：1
     *      *    2、2级  走法：2      11   2
     *      *    3、3级  走法：4     111  12 21 3
     *      *    4、4级  走法：7
     *
     *      *    5、5级  走法：13
     *    n：规模
     *    结论： 当前台阶的级数走法=之前最近3个台阶的级数走法之和
     * @param n     时间复杂度： O(3^n)  空间复杂度 O(1) [ (堆）    +    255MB（栈） ]
     * @return
     */
    private static long f(long n) {//50   6
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        if(n == 3){
            return 4;
        }
        //大于等于4  不能小于4
        return f(n-1) + f(n-2) + f(n-3);//裂项式递归  O(3^n)
    }
}
